package com.gorkr.labuladong.data_struct.graph;

import java.util.LinkedList;
import java.util.List;

/**
 * @author gorkr
 * @date 2022/06/10 09:26
 **/
public class M797AllPathsFromSourceToTarget {

    private LinkedList<List<Integer>> res;

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        res = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        traverse(graph, 0, path);
        return res;
    }

    private void traverse(int[][] graph, int s, LinkedList<Integer> path) {
        path.add(s);
        if(s == graph.length-1){
            res.add(new LinkedList<>(path));
        }


        for (int child : graph[s]) {
            traverse(graph, child, path);
        }

        path.removeLast();
    }
}
    